package nowcoderLinkList;

import java.util.*;


public class nowCoderBinaryTree {

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode (int val) {
            this.val = val;
        }
    }
    public TreeNode createBinaryTree() {
        TreeNode root = new TreeNode(1);
        TreeNode n1 = new TreeNode(2);
        TreeNode n2 = new TreeNode(3);
        TreeNode n3 = new TreeNode(4);
        TreeNode n4 = new TreeNode(5);
        TreeNode n5 = new TreeNode(6);

        root.left = n1;
        root.right = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        return root;
    }
    /*newCoder 刷题&&  */
    //二叉树的层序遍历   有返回值
    //返回的是一个二维数组
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            ArrayList<Integer> arrayList = new ArrayList<>();
            int size = queue.size();
            while (size != 0) {
                TreeNode cur = queue.poll();
                size--;
                //arrayList.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(arrayList);
        }
        return list;
    }

    //获取二叉树的高度
    public int maxDepth (TreeNode root) {
        // write code here
        if (root == null) {
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        int maxHeight = leftHeight < rightHeight ? rightHeight : leftHeight;
        return maxHeight + 1;
    }

    //29 二叉树中和为某一值的路径(一)
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        return false;
    }

    //31 对称的二叉树  思路：判断子树是否对称
    public boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null) return true;
        return isSymmetricalChild(pRoot.left,pRoot.right);
    }
    public boolean isSymmetricalChild(TreeNode leftRoot,TreeNode rightRoot) {
        //两边都空：
        if (leftRoot == null && rightRoot == null) return true;
        //只要有一边是空的，或者值不想等：
        if (leftRoot == null || rightRoot == null ||
                leftRoot.val != rightRoot.val) {
            return false;
        }
        return isSymmetricalChild(leftRoot.left,rightRoot.right) &&
                isSymmetricalChild(leftRoot.right,rightRoot.left);
    }

    //32 合并二叉树
    /*public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        //两边都是空的
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        TreeNode newRoot = new TreeNode();
        newRoot.val = t1.val + t2.val;
        newRoot.left = mergeTrees(t1.left,t2.left);
        newRoot.right = mergeTrees(t1.right,t2.right);
        return newRoot;
    }*/

    //33 二叉树的镜像  就是反转一颗二叉树
    public TreeNode Mirror1 (TreeNode pRoot) {
        // write code here
        if (pRoot == null) return null;
        TreeNode tmp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = tmp;
        Mirror1(pRoot.left);
        Mirror1(pRoot.right);
        return pRoot;
    }
    public TreeNode Mirror (TreeNode pRoot) {
        if (pRoot == null) return null;
        TreeNode left = Mirror(pRoot.left);
        TreeNode right = Mirror(pRoot.right);
        pRoot.left = right;
        pRoot.right = left;
        return pRoot;
    }

    //34 判断是不是二叉搜索树
    public boolean isValidBST (TreeNode root) {
        // write code here
        return false;
    }

    //35 判断是不是完全二叉树
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean first = false;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur == null) {
                first = true;
                continue;
            }
            if (first) return false;
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        return true;
    }
    //36 判断是不是平衡二叉树   判断左子树和右子树是否平衡
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) return true;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if (Math.abs(leftHeight-rightHeight) <= 1) return true;
       return IsBalanced_Solution(root.left) &&
               IsBalanced_Solution(root.right);
    }

    public int getHeight(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight,rightHeight) + 1;
    }

    //37 二叉搜索树的最近公共祖先
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        return -1;
    }
}










